/*
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? 
Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.
*/
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> total;
        int n = nums.size();
        if(n<4)  return total;
        sort(nums.begin(),nums.end());
        for(int i=0;i<n-3;i++)
        {
            if(i>0&&nums[i]==nums[i-1]) continue;
            if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break;
            if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target) continue;
            for(int j=i+1;j<n-2;j++)
            {
                if(j>i+1&&nums[j]==nums[j-1]) continue;
                if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break;
                if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target) continue;
                int left=j+1,right=n-1;
                while(left<right){
                    int sum=nums[left]+nums[right]+nums[i]+nums[j];
                    if(sum<target) left++;
                    else if(sum>target) right--;
                    else{
                        total.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
                        do{left++;}while(nums[left]==nums[left-1]&&left<right);
                        do{right--;}while(nums[right]==nums[right+1]&&left<right);
                    }
                }
            }
        }
        return total;
    }
};

class Solution {
private:
    const int K = 4;
    int size;
    void search(const vector<int>& nums, int pos, int k, int target, vector<int>& v, vector<vector<int>>& vv)
    {
        if(k == 2)
        {
            int l = pos, r = size-1;
            while(l < r)
            {
                int t = nums[l]+nums[r];
                if(t > target) r--;
                else if(t < target) l++;
                else
                {
                    v.push_back(nums[l++]);
                    v.push_back(nums[r--]);
                    vv.push_back(v);
                    v.pop_back(), v.pop_back();
                    while(l<r && nums[l]==nums[l-1]) l++;
                    while(l<r && nums[r]==nums[r+1]) r--;
                }
            }
        }
        else
        {
            for(int j = pos; j <= size-k; ++j)
            {
                int sum = 0;
                for(int i = j; i < k+j; ++i) sum += nums[i];
                if(sum > target) break;
                sum = nums[j];
                for(int i = 0; i < k-1; ++i) sum += nums[size-1-i];
                if(sum < target) continue;
                v.push_back(nums[j]);
                search(nums, j+1, k-1, target-nums[j], v, vv);
                v.pop_back();
                while(j<=size-k && nums[j+1]==nums[j]) j++;
            }
        }
    }
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        sort(nums.begin(), nums.end());
        size = nums.size();
        vector<int> v;
        vector<vector<int>> vv;
        search(nums, 0, K, target, v, vv);
        return vv;
    }
};